1
運輸網絡的結構分析
MATH002Lesson 10
00:00

運輸網絡是一種專門的數學結構，用於模擬商品、資料或物料透過受限制通道系統的流動。它通過指定特定的起點與終點，將一個標準的有向圖轉化為一個功能性框架，同時在系統內每條連接上施加物理性的「瓶頸」限制。

運輸網絡的定義

根據 定義 10.1.1，運輸網絡（或簡稱網絡）是一個簡單、加權、有向圖，必須滿足三個核心條件：

性質 (a)：源點

一個指定的頂點，即 源點 （$a$ 或 $s$），代表起點。其入度為零（無任何邊進入），作為無限供應者。

性質 (b)：匯點

一個指定的頂點，即 匯點 （$z$ 或 $t$），代表最終消費端。其出度為零（無任何邊離開）。

性質 (c)：容量

每條有向邊 $(i, j)$ 的權重 $C_{ij}$ 稱為其 容量。該值必須為非負數（$C_{ij} \geq 0$），表示該邊所能支援的最大流量。

現實案例類比：區域電力網絡

為了讓這些抽象概念具體化，請考慮一個區域性電力網絡：

  • 源點： 一座大型水力發電大壩。它僅產生能量；電力不會從電網本身流入大壩。
  • 匯點： 一個重工業製造區。它消耗所有流入的電力以驅動機械設備；沒有電力回饋至電網。
  • 邊與容量： 傳輸線路即為邊。其容量是物理導線在因過熱而失效前可承受的最大電流。
  • 中間節點： 本地變電站，負責重新導引流動但不「消耗」電力（流量守恆）。

容量與流量的差異

關鍵在於區分 容量 與 流量。容量 $C_{ij}$ 是靜態的物理特性——代表潛在體積。流量 $F_{ij}$ 則是某一時刻實際移動的體積。在此頁面中，我們專注於 結構限制 （容量），而非當前的流動狀態。

🎯 核心原則：結構約束
每個運輸網絡都是有向圖，其中流量從供應商（源點）經由容量為非負數的管道流向消費者（匯點）。
源點：$deg^-(a) = 0 \quad | \quad$ 匯點：$deg^+(z) = 0 \quad | \quad \text{容量}：C_{ij} \geq 0